833B - The Bakery - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define sz(a) ((int) a.size())
#define ls u << 1
#define rs u << 1 | 1
const int N = 1e5 + 15;
int n, k, a[N];
int lt[N], lst[N], dp[N];
int tr[N << 2];
int kp[N << 2];
void push(int u) {
	kp[ls] += kp[u];
	tr[ls] += kp[u];
	tr[rs] += kp[u];
	kp[rs] += kp[u];
	kp[u] = 0; 
}
void build(int u, int l, int r) {
	kp[u] = 0;
	if(l == r) {
		tr[u] = dp[l];
		return;
	}
	int m = (l + r) / 2;
	build(ls, l, m);
	build(rs, m + 1, r);
	tr[u] = max(tr[ls], tr[rs]);
}
int get(int ql, int qr, int u = 1, int l = 0, int r = n) {
	push(u);
	if(ql > qr or ql > r or l > qr) return 0;
	if(ql <= l && r <= qr) return tr[u];
	int m = (l + r) / 2;
	return max(get(ql, qr, ls, l, m), get(ql, qr, rs, m + 1, r)); 
}
void upd(int ql, int qr, int u = 1, int l = 0, int r = n) {
	push(u);
	if(ql > qr or ql > r or l > qr) return;
	if(ql <= l && r <= qr) {
		tr[u] += 1;
		kp[u] += 1;
		return;
	}
	int m = (l + r) / 2;
	upd(ql, qr, ls, l, m);
	upd(ql, qr, rs, m + 1, r);
	tr[u] = max(tr[ls], tr[rs]);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		lt[i] = lst[a[i]];
		lst[a[i]] = i;
	}
	for(int i = 1; i <= n; i++) dp[i] = -n;
	dp[0] = 0;
	for(int j = 1; j <= k; j++) {
		build(1, 0, n);
		for(int i = 0; i <= n; i++) {
			upd(lt[i], i - 1);
			dp[i] = get(0, i - 1);
		}
	}
	cout << dp[n] << '\n';
}